
import java.util.*;
/**
 * 
 * 字符串的排列
 * 
 * 描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围：
n
<
10
n<10
要求：空间复杂度 
O
(
n
!
)
O(n!)，时间复杂度 
O
(
n
!
)
O(n!)
输入描述：

输入一个字符串,长度不超过10,字符只包括大小写字母。
 */
public class 字符串的排列 {
    
    public static void main(String[] args) {
        
        String str = "qwertyuio";

        Permutation(str).forEach(System.out::println);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public static ArrayList<String> Permutation (String str) {
        // write code here
        if (str == null || str.equals("")) {
            return res;
        }
        char[] strs = str.toCharArray();
        Arrays.sort(strs);
        visited = new boolean[strs.length];
        combination(strs, 0);
        res.addAll(paths);
        return res;
    
    }
 
    private static ArrayList<String> res = new ArrayList<>();
    private static TreeSet<String> paths = new TreeSet<>();
    private static StringBuilder path = new StringBuilder();
    private static boolean[] visited;

    private static void combination(char[] strs, int len) {
        if (len == strs.length) {
            paths.add(path.toString());
            return;
        }
        for (int i = 0; i < strs.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                path.append(strs[i]);
                combination(strs, len + 1);
                //Duang ~ 回溯 - 状态重置
                visited[i] = false;
                path.deleteCharAt(path.length() - 1);
            }
        }
    }

}
